#include <stdio.h>
#include <stdlib.h>

int compare_int(const void* p1, const void* p2) {
    int* a = (int*)(p1);
    int* b = (int*)(p2);
    return *a<=*b;
}

void print_int_array(int* a, int size) {
    int i;
    for(i=0;i<size;i++) {
        printf("%d\t", a[i]);
    }
    printf("\n");
}


void merge(void* data, int data_size, int s, int e, void* tmp1, void* tmp2, int tmplen1, int tmplen2, int (*compare)(const void*, const void*)) {
    int iter1 = 0;
    int iter2 = 0;
    int iter = s;

    while(iter1<tmplen1 && iter2<tmplen2) {
        if(compare(tmp1+iter1*data_size, tmp2+iter2*data_size)) {
            memcpy(data+iter*data_size, tmp1+iter1*data_size, data_size);
            iter1++;
        } else {
            memcpy(data+iter*data_size, tmp2+iter2*data_size, data_size);
            iter2++;
        }
        iter++;
    }
    while(iter1<tmplen1) {
        memcpy(data+iter*data_size, tmp1+iter1*data_size, data_size);
        iter1++;
        iter++;
    }
    while(iter2<tmplen2) {
        memcpy(data+iter*data_size, tmp2+iter2*data_size, data_size);
        iter2++;
        iter++;
    }
    return;
}

void mergeSort(void* data, int data_size, int s, int e, int (*compare)(const void*, const void*)) {
    if(e-s+1 <= 1) {
        // less than one element
        return;
    }

    int middle = s+(e-s)/2;

    mergeSort(data, data_size, s, middle, compare);
    mergeSort(data, data_size, middle+1, e, compare);

    void* tmp1 = malloc((middle-s+1)*data_size);
    void* tmp2 = malloc((e-middle)*data_size);

    memcpy(tmp1, data+s*data_size, (middle-s+1)*data_size);
    memcpy(tmp2, data+(middle+1)*data_size, (e-middle)*data_size);


    /*
       printf("===========\n");
       printf("data:\n");
       print_int_array(data+s*data_size, e-s+1);

       printf("tmp1:\n");
       print_int_array(tmp1, middle-s+1);

       printf("tmp2:\n");
       print_int_array(tmp2, e-middle);
       */

    merge(data, data_size, s, e, tmp1, tmp2, middle-s+1, e-middle, compare);

    /*
       printf("after merge data:\n");
       print_int_array(data+s*data_size, e-s+1);
       printf("===========\n");
       */

    free(tmp1);
    free(tmp2);
    return;
}

int main() {
    const int array_size = 4;
    int a[5] = {213, -12, -12, -5656};
    mergeSort(a, sizeof(int), 0, array_size-1, compare_int);
    print_int_array(a, array_size);
    return 0;
}
